class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if(matrix.empty())
            return {};

        int left = 0;
        int right = matrix[0].size() - 1;
        int up = 0;
        int down = matrix.size() - 1;
        vector<int> ret;
        ret.reserve((right + 1) * (down + 1));


        while(1)
        {
            // 从左到右
            for(int i = left; i <= right; i++)
                ret.push_back(matrix[up][i]);
            up++;       // 上边界下移
            if(up > down)
                break;

            // 从上到下
            for(int i = up; i <= down; i++)
                ret.push_back(matrix[i][right]);
            right--;    // 右边界左移
            if(right < left)
                break;

            // 从右到左
            for(int i = right; i >= left; i--)
                ret.push_back(matrix[down][i]);
            down--;     // 下边界上移
            if(down < up)
                break;

            // 从下到上
            for(int i = down; i >= up; i--)
                ret.push_back(matrix[i][left]);
            left++;     // 左边界右移
            if(left > right)
                break;
        }
        return ret;
    }
};